package _hash

import org.junit.Assert
import org.junit.Test

/*
https://programmercarl.com/0018.%E5%9B%9B%E6%95%B0%E4%B9%8B%E5%92%8C.html
https://leetcode.cn/problems/4sum/description/
18. 四数之和
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
 */
class leetcode_18 {
    @Test
    fun test_1() {
        val actual = fourSum(intArrayOf(1, 0, -1, 0, -2, 2), target = 0)
        val expect: ArrayList<ArrayList<Int>> = arrayListOf(arrayListOf(-2, -1, 1, 2), arrayListOf(-2, 0, 0, 2), arrayListOf(-1, 0, 0, 1))
        Assert.assertEquals(expect.joinToString(), actual.joinToString())
    }

    @Test
    fun test_2() {
        val actual = fourSum(intArrayOf(2, 2, 2, 2, 2), target = 8)
        val expect: ArrayList<ArrayList<Int>> = arrayListOf(arrayListOf(2, 2, 2, 2))
        Assert.assertEquals(expect.joinToString(), actual.joinToString())
    }

    fun fourSum(nums: IntArray, target: Int): List<List<Int>> {
        /**
         * sort
         * loop i to end{
         *  if(i v > 0 && target > 0 && i v > target) return
         *  if( i -1 > 0 && i == i-1){
         *      skip
         *  }
         *  loop j= i+1 to end{
         *      if(i + j v > target && i + j v > 0) break
         *      if( j > i + 1 && j = j-1) skip
         *
         *      left = j + 1
         *      right = end
         *      sum = nums[i] + nums[j] + nums[left] + nums[right]
         *      if(sum == 0){
         *          add to list
         *          while(right > left and right v = right-1 v) right--
         *          while(right > left and left v == left + 1 v)left++
         *          left++
         *          right--
         *      }
         *      else if(sum < 0){
         *          left++
         *      }
         *      else{
         *          right--
         * }
         *
         */

        nums.sort()
        val end: Int = nums.size - 1
        val list: ArrayList<ArrayList<Int>> = ArrayList<ArrayList<Int>>()
        var left: Int
        var right: Int
        var sum: Int
        for (i in 0..end) {
            if (nums[i] > 0 && target > 0 && nums[i] > target) return list
            if (i - 1 >= 0 && nums[i] == nums[i - 1]) continue
            for (j in i + 1..end) {
                if (nums[i] + nums[j] > target && nums[i] + nums[j] > 0) break
//                if (j > i + 1 && nums[j] == nums[j - 1]) continue
                if (j > i + 1 && nums[j] == nums[j - 1]) continue
                left = j + 1
                right = end
                while (right > left) {
                    sum = nums[i] + nums[j] + nums[left] + nums[right]
                    if (sum == target) {
                        list.add(arrayListOf(nums[i], nums[j], nums[left], nums[right]))
                        while (right > left && nums[right] == nums[right - 1]) right--
                        while (right > left && nums[left] == nums[left + 1]) left++
                        left++
                        right--
                    } else if (sum < target) {
                        left++
                    } else {
                        right--
                    }
                }
            }
        }
        return list
    }
}